Runtime Complexity (innermost) proof of /tmp/tmpIeLkRU/Ex5_DLMMU04

The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).

0 CpxTRS

↳1 DependencyGraphProof (BOTH BOUNDS(ID, ID), 0 ms)

↳2 CpxTRS

↳3 TrsToWeightedTrsProof (BOTH BOUNDS(ID, ID), 0 ms)

↳4 CpxWeightedTrs

↳5 InnermostUnusableRulesProof (BOTH BOUNDS(ID, ID), 0 ms)

↳6 CpxWeightedTrs

↳7 TypeInferenceProof (BOTH BOUNDS(ID, ID), 0 ms)

↳8 CpxTypedWeightedTrs

↳9 CompletionProof (UPPER BOUND(ID), 7 ms)

↳10 CpxTypedWeightedCompleteTrs

↳11 CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID), 0 ms)

↳12 CpxRNTS

↳13 CompleteCoflocoProof (⇔, 361 ms)

↳14 BOUNDS(1, n^1)

(0) Obligation:

The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).

The TRS R consists of the following rules:

pairNs → cons(0, n__incr(n__oddNs))
oddNs → incr(pairNs)
incr(cons(X, XS)) → cons(s(X), n__incr(activate(XS)))
take(0, XS) → nil
take(s(N), cons(X, XS)) → cons(X, n__take(N, activate(XS)))
zip(nil, XS) → nil
zip(X, nil) → nil
zip(cons(X, XS), cons(Y, YS)) → cons(pair(X, Y), n__zip(activate(XS), activate(YS)))
tail(cons(X, XS)) → activate(XS)
repItems(nil) → nil
repItems(cons(X, XS)) → cons(X, n__cons(X, n__repItems(activate(XS))))
incr(X) → n__incr(X)
oddNs → n__oddNs
take(X1, X2) → n__take(X1, X2)
zip(X1, X2) → n__zip(X1, X2)
cons(X1, X2) → n__cons(X1, X2)
repItems(X) → n__repItems(X)
activate(n__incr(X)) → incr(activate(X))
activate(n__oddNs) → oddNs
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(n__zip(X1, X2)) → zip(activate(X1), activate(X2))
activate(n__cons(X1, X2)) → cons(activate(X1), X2)
activate(n__repItems(X)) → repItems(activate(X))
activate(X) → X

Rewrite Strategy: INNERMOST

(1) DependencyGraphProof (BOTH BOUNDS(ID, ID) transformation)

The following rules are not reachable from basic terms in the dependency graph and can be removed:
tail(cons(X, XS)) → activate(XS)

(2) Obligation:

The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1).

The TRS R consists of the following rules:

zip(nil, XS) → nil
zip(X, nil) → nil
repItems(X) → n__repItems(X)
activate(n__repItems(X)) → repItems(activate(X))
take(s(N), cons(X, XS)) → cons(X, n__take(N, activate(XS)))
activate(X) → X
activate(n__incr(X)) → incr(activate(X))
cons(X1, X2) → n__cons(X1, X2)
incr(cons(X, XS)) → cons(s(X), n__incr(activate(XS)))
oddNs → n__oddNs
take(X1, X2) → n__take(X1, X2)
repItems(cons(X, XS)) → cons(X, n__cons(X, n__repItems(activate(XS))))
zip(cons(X, XS), cons(Y, YS)) → cons(pair(X, Y), n__zip(activate(XS), activate(YS)))
incr(X) → n__incr(X)
activate(n__zip(X1, X2)) → zip(activate(X1), activate(X2))
repItems(nil) → nil
take(0, XS) → nil
activate(n__take(X1, X2)) → take(activate(X1), activate(X2))
activate(n__oddNs) → oddNs
pairNs → cons(0, n__incr(n__oddNs))
oddNs → incr(pairNs)
zip(X1, X2) → n__zip(X1, X2)
activate(n__cons(X1, X2)) → cons(activate(X1), X2)

Rewrite Strategy: INNERMOST

(3) TrsToWeightedTrsProof (BOTH BOUNDS(ID, ID) transformation)

Transformed TRS to weighted TRS

(4) Obligation:

The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).

The TRS R consists of the following rules:

zip(nil, XS) → nil [1]
zip(X, nil) → nil [1]
repItems(X) → n__repItems(X) [1]
activate(n__repItems(X)) → repItems(activate(X)) [1]
take(s(N), cons(X, XS)) → cons(X, n__take(N, activate(XS))) [1]
activate(X) → X [1]
activate(n__incr(X)) → incr(activate(X)) [1]
cons(X1, X2) → n__cons(X1, X2) [1]
incr(cons(X, XS)) → cons(s(X), n__incr(activate(XS))) [1]
oddNs → n__oddNs [1]
take(X1, X2) → n__take(X1, X2) [1]
repItems(cons(X, XS)) → cons(X, n__cons(X, n__repItems(activate(XS)))) [1]
zip(cons(X, XS), cons(Y, YS)) → cons(pair(X, Y), n__zip(activate(XS), activate(YS))) [1]
incr(X) → n__incr(X) [1]
activate(n__zip(X1, X2)) → zip(activate(X1), activate(X2)) [1]
repItems(nil) → nil [1]
take(0, XS) → nil [1]
activate(n__take(X1, X2)) → take(activate(X1), activate(X2)) [1]
activate(n__oddNs) → oddNs [1]
pairNs → cons(0, n__incr(n__oddNs)) [1]
oddNs → incr(pairNs) [1]
zip(X1, X2) → n__zip(X1, X2) [1]
activate(n__cons(X1, X2)) → cons(activate(X1), X2) [1]

Rewrite Strategy: INNERMOST

(5) InnermostUnusableRulesProof (BOTH BOUNDS(ID, ID) transformation)

Removed the following rules with non-basic left-hand side, as they cannot be used in innermost rewriting:

take(s(N), cons(X, XS)) → cons(X, n__take(N, activate(XS))) [1]
incr(cons(X, XS)) → cons(s(X), n__incr(activate(XS))) [1]
repItems(cons(X, XS)) → cons(X, n__cons(X, n__repItems(activate(XS)))) [1]
zip(cons(X, XS), cons(Y, YS)) → cons(pair(X, Y), n__zip(activate(XS), activate(YS))) [1]

Due to the following rules that have to be used instead:

cons(X1, X2) → n__cons(X1, X2) [1]

(6) Obligation:

The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1).

The TRS R consists of the following rules:

zip(nil, XS) → nil [1]
zip(X, nil) → nil [1]
repItems(X) → n__repItems(X) [1]
activate(n__repItems(X)) → repItems(activate(X)) [1]
activate(X) → X [1]
activate(n__incr(X)) → incr(activate(X)) [1]
cons(X1, X2) → n__cons(X1, X2) [1]
oddNs → n__oddNs [1]
take(X1, X2) → n__take(X1, X2) [1]
incr(X) → n__incr(X) [1]
activate(n__zip(X1, X2)) → zip(activate(X1), activate(X2)) [1]
repItems(nil) → nil [1]
take(0, XS) → nil [1]
activate(n__take(X1, X2)) → take(activate(X1), activate(X2)) [1]
activate(n__oddNs) → oddNs [1]
pairNs → cons(0, n__incr(n__oddNs)) [1]
oddNs → incr(pairNs) [1]
zip(X1, X2) → n__zip(X1, X2) [1]
activate(n__cons(X1, X2)) → cons(activate(X1), X2) [1]

Rewrite Strategy: INNERMOST

(7) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)

Infered types.

(8) Obligation:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

zip(nil, XS) → nil [1]
zip(X, nil) → nil [1]
repItems(X) → n__repItems(X) [1]
activate(n__repItems(X)) → repItems(activate(X)) [1]
activate(X) → X [1]
activate(n__incr(X)) → incr(activate(X)) [1]
cons(X1, X2) → n__cons(X1, X2) [1]
oddNs → n__oddNs [1]
take(X1, X2) → n__take(X1, X2) [1]
incr(X) → n__incr(X) [1]
activate(n__zip(X1, X2)) → zip(activate(X1), activate(X2)) [1]
repItems(nil) → nil [1]
take(0, XS) → nil [1]
activate(n__take(X1, X2)) → take(activate(X1), activate(X2)) [1]
activate(n__oddNs) → oddNs [1]
pairNs → cons(0, n__incr(n__oddNs)) [1]
oddNs → incr(pairNs) [1]
zip(X1, X2) → n__zip(X1, X2) [1]
activate(n__cons(X1, X2)) → cons(activate(X1), X2) [1]

The TRS has the following type information:

zip :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
nil :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
repItems :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
n__repItems :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
activate :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
n__incr :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
incr :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
cons :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
n__cons :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
oddNs :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
n__oddNs :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
take :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
n__take :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
n__zip :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0 → nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
0 :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0
pairNs :: nil:n__repItems:n__incr:n__cons:n__oddNs:n__take:n__zip:0

Rewrite Strategy: INNERMOST

(9) CompletionProof (UPPER BOUND(ID) transformation)

The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added:
none

And the following fresh constants: none

(10) Obligation:

Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is:

Runtime Complexity Weighted TRS with Types.
The TRS R consists of the following rules:

zip(nil, XS) → nil [1]
zip(X, nil) → nil [1]
repItems(X) → n__repItems(X) [1]
activate(n__repItems(X)) → repItems(activate(X)) [1]
activate(X) → X [1]
activate(n__incr(X)) → incr(activate(X)) [1]
cons(X1, X2) → n__cons(X1, X2) [1]
oddNs → n__oddNs [1]
take(X1, X2) → n__take(X1, X2) [1]
incr(X) → n__incr(X) [1]
activate(n__zip(X1, X2)) → zip(activate(X1), activate(X2)) [1]
repItems(nil) → nil [1]
take(0, XS) → nil [1]
activate(n__take(X1, X2)) → take(activate(X1), activate(X2)) [1]
activate(n__oddNs) → oddNs [1]
pairNs → cons(0, n__incr(n__oddNs)) [1]
oddNs → incr(pairNs) [1]
zip(X1, X2) → n__zip(X1, X2) [1]
activate(n__cons(X1, X2)) → cons(activate(X1), X2) [1]

The TRS has the following type information:

Rewrite Strategy: INNERMOST

(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID) transformation)

Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction.
The constant constructors are abstracted as follows:

nil => 2
n__oddNs => 1
0 => 0

(12) Obligation:

Complexity RNTS consisting of the following rules:

activate(z) -{ 1 }→ X :|: X >= 0, z = X
activate(z) -{ 1 }→ zip(activate(X1), activate(X2)) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
activate(z) -{ 1 }→ take(activate(X1), activate(X2)) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
activate(z) -{ 1 }→ repItems(activate(X)) :|: z = 1 + X, X >= 0
activate(z) -{ 1 }→ oddNs :|: z = 1
activate(z) -{ 1 }→ incr(activate(X)) :|: z = 1 + X, X >= 0
activate(z) -{ 1 }→ cons(activate(X1), X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2
cons(z, z') -{ 1 }→ 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2
incr(z) -{ 1 }→ 1 + X :|: X >= 0, z = X
oddNs -{ 1 }→ incr(pairNs) :|:
oddNs -{ 1 }→ 1 :|:
pairNs -{ 1 }→ cons(0, 1 + 1) :|:
repItems(z) -{ 1 }→ 2 :|: z = 2
repItems(z) -{ 1 }→ 1 + X :|: X >= 0, z = X
take(z, z') -{ 1 }→ 2 :|: z' = XS, z = 0, XS >= 0
take(z, z') -{ 1 }→ 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2
zip(z, z') -{ 1 }→ 2 :|: z = 2, z' = XS, XS >= 0
zip(z, z') -{ 1 }→ 2 :|: z' = 2, X >= 0, z = X
zip(z, z') -{ 1 }→ 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2

Only complete derivations are relevant for the runtime complexity.

(13) CompleteCoflocoProof (EQUIVALENT transformation)

Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo:

eq(start(V, V1),0,[zip(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1),0,[repItems(V, Out)],[V >= 0]).
eq(start(V, V1),0,[activate(V, Out)],[V >= 0]).
eq(start(V, V1),0,[cons(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1),0,[oddNs(Out)],[]).
eq(start(V, V1),0,[take(V, V1, Out)],[V >= 0,V1 >= 0]).
eq(start(V, V1),0,[incr(V, Out)],[V >= 0]).
eq(start(V, V1),0,[pairNs(Out)],[]).
eq(zip(V, V1, Out),1,[],[Out = 2,V = 2,V1 = XS1,XS1 >= 0]).
eq(zip(V, V1, Out),1,[],[Out = 2,V1 = 2,X3 >= 0,V = X3]).
eq(repItems(V, Out),1,[],[Out = 1 + X4,X4 >= 0,V = X4]).
eq(activate(V, Out),1,[activate(X5, Ret0),repItems(Ret0, Ret)],[Out = Ret,V = 1 + X5,X5 >= 0]).
eq(activate(V, Out),1,[],[Out = X6,X6 >= 0,V = X6]).
eq(activate(V, Out),1,[activate(X7, Ret01),incr(Ret01, Ret1)],[Out = Ret1,V = 1 + X7,X7 >= 0]).
eq(cons(V, V1, Out),1,[],[Out = 1 + X11 + X21,X11 >= 0,X21 >= 0,V = X11,V1 = X21]).
eq(oddNs(Out),1,[],[Out = 1]).
eq(take(V, V1, Out),1,[],[Out = 1 + X12 + X22,X12 >= 0,X22 >= 0,V = X12,V1 = X22]).
eq(incr(V, Out),1,[],[Out = 1 + X8,X8 >= 0,V = X8]).
eq(activate(V, Out),1,[activate(X13, Ret02),activate(X23, Ret11),zip(Ret02, Ret11, Ret2)],[Out = Ret2,X13 >= 0,X23 >= 0,V = 1 + X13 + X23]).
eq(repItems(V, Out),1,[],[Out = 2,V = 2]).
eq(take(V, V1, Out),1,[],[Out = 2,V1 = XS2,V = 0,XS2 >= 0]).
eq(activate(V, Out),1,[activate(X14, Ret03),activate(X24, Ret12),take(Ret03, Ret12, Ret3)],[Out = Ret3,X14 >= 0,X24 >= 0,V = 1 + X14 + X24]).
eq(activate(V, Out),1,[oddNs(Ret4)],[Out = Ret4,V = 1]).
eq(pairNs(Out),1,[cons(0, 1 + 1, Ret5)],[Out = Ret5]).
eq(oddNs(Out),1,[pairNs(Ret04),incr(Ret04, Ret6)],[Out = Ret6]).
eq(zip(V, V1, Out),1,[],[Out = 1 + X15 + X25,X15 >= 0,X25 >= 0,V = X15,V1 = X25]).
eq(activate(V, Out),1,[activate(X16, Ret05),cons(Ret05, X26, Ret7)],[Out = Ret7,X16 >= 0,X26 >= 0,V = 1 + X16 + X26]).
input_output_vars(zip(V,V1,Out),[V,V1],[Out]).
input_output_vars(repItems(V,Out),[V],[Out]).
input_output_vars(activate(V,Out),[V],[Out]).
input_output_vars(cons(V,V1,Out),[V,V1],[Out]).
input_output_vars(oddNs(Out),[],[Out]).
input_output_vars(take(V,V1,Out),[V,V1],[Out]).
input_output_vars(incr(V,Out),[V],[Out]).
input_output_vars(pairNs(Out),[],[Out]).

CoFloCo proof output:
Preprocessing Cost Relations
=====================================

#### Computed strongly connected components
0. non_recursive : [cons/3]
1. non_recursive : [incr/2]
2. non_recursive : [pairNs/1]
3. non_recursive : [oddNs/1]
4. non_recursive : [repItems/2]
5. non_recursive : [take/3]
6. non_recursive : [zip/3]
7. recursive [non_tail,multiple] : [activate/2]
8. non_recursive : [start/2]

#### Obtained direct recursion through partial evaluation
0. SCC is completely evaluated into other SCCs
1. SCC is completely evaluated into other SCCs
2. SCC is completely evaluated into other SCCs
3. SCC is partially evaluated into oddNs/1
4. SCC is partially evaluated into repItems/2
5. SCC is partially evaluated into take/3
6. SCC is partially evaluated into zip/3
7. SCC is partially evaluated into activate/2
8. SCC is partially evaluated into start/2

Control-Flow Refinement of Cost Relations
=====================================

### Specialization of cost equations oddNs/1
* CE 21 is refined into CE [24]
* CE 20 is refined into CE [25]

### Cost equations --> "Loop" of oddNs/1
* CEs [24] --> Loop 16
* CEs [25] --> Loop 17

### Ranking functions of CR oddNs(Out)

#### Partial ranking functions of CR oddNs(Out)

### Specialization of cost equations repItems/2
* CE 12 is refined into CE [26]
* CE 13 is refined into CE [27]

### Cost equations --> "Loop" of repItems/2
* CEs [26] --> Loop 18
* CEs [27] --> Loop 19

### Ranking functions of CR repItems(V,Out)

#### Partial ranking functions of CR repItems(V,Out)

### Specialization of cost equations take/3
* CE 22 is refined into CE [28]
* CE 23 is refined into CE [29]

### Cost equations --> "Loop" of take/3
* CEs [28] --> Loop 20
* CEs [29] --> Loop 21

### Ranking functions of CR take(V,V1,Out)

#### Partial ranking functions of CR take(V,V1,Out)

### Specialization of cost equations zip/3
* CE 11 is refined into CE [30]
* CE 10 is refined into CE [31]
* CE 9 is refined into CE [32]

### Cost equations --> "Loop" of zip/3
* CEs [30] --> Loop 22
* CEs [31] --> Loop 23
* CEs [32] --> Loop 24

### Ranking functions of CR zip(V,V1,Out)

#### Partial ranking functions of CR zip(V,V1,Out)

### Specialization of cost equations activate/2
* CE 16 is refined into CE [33]
* CE 14 is refined into CE [34,35]
* CE 15 is refined into CE [36]
* CE 19 is refined into CE [37,38]
* CE 17 is refined into CE [39,40,41]
* CE 18 is refined into CE [42,43]

### Cost equations --> "Loop" of activate/2
* CEs [41,43] --> Loop 25
* CEs [40] --> Loop 26
* CEs [39] --> Loop 27
* CEs [42] --> Loop 28
* CEs [38] --> Loop 29
* CEs [36,37] --> Loop 30
* CEs [33,35] --> Loop 31
* CEs [34] --> Loop 32

### Ranking functions of CR activate(V,Out)
* RF of phase [25,26,27,28,31,32]: [V]

#### Partial ranking functions of CR activate(V,Out)
* Partial RF of phase [25,26,27,28,31,32]:
- RF of loop [25:1,25:2,26:1,26:2,27:1,27:2,28:1,28:2,31:1,32:1]:
V

### Specialization of cost equations start/2
* CE 2 is refined into CE [44,45,46]
* CE 3 is refined into CE [47,48]
* CE 4 is refined into CE [49,50,51]
* CE 5 is refined into CE [52]
* CE 6 is refined into CE [53,54]
* CE 7 is refined into CE [55,56]
* CE 8 is refined into CE [57]

### Cost equations --> "Loop" of start/2
* CEs [44,45,46,47,48,49,50,51,52,53,54,55,56,57] --> Loop 33

### Ranking functions of CR start(V,V1)

#### Partial ranking functions of CR start(V,V1)

Computing Bounds
=====================================

#### Cost of chains of oddNs(Out):
* Chain [17]: 1
with precondition: [Out=1]

* Chain [16]: 4
with precondition: [Out=4]

#### Cost of chains of repItems(V,Out):
* Chain [19]: 1
with precondition: [V=2,Out=2]

* Chain [18]: 1
with precondition: [V+1=Out,V>=0]

#### Cost of chains of take(V,V1,Out):
* Chain [21]: 1
with precondition: [V=0,Out=2,V1>=0]

* Chain [20]: 1
with precondition: [V+V1+1=Out,V>=0,V1>=0]

#### Cost of chains of zip(V,V1,Out):
* Chain [24]: 1
with precondition: [V=2,Out=2,V1>=0]

* Chain [23]: 1
with precondition: [V1=2,Out=2,V>=0]

* Chain [22]: 1
with precondition: [V+V1+1=Out,V>=0,V1>=0]

#### Cost of chains of activate(V,Out):
* Chain [30]: 2
with precondition: [V=Out,V>=0]

* Chain [29]: 5
with precondition: [V=1,Out=4]

* Chain [multiple([25,26,27,28,31,32],[[30],[29]])]: 2*it(25)+4*it(26)+6*it(28)+5*it([29])+2*it([30])+0
Such that:it([30]) =< V+1
it([29]) =< V/2+1/2
aux(1) =< V
aux(2) =< 5/2*V+3/2
aux(3) =< 20/19*V+1/19
it(28) =< aux(1)
it([29]) =< aux(1)
it(25) =< aux(2)
it(26) =< aux(2)
it(28) =< aux(2)
it([29]) =< aux(2)
it([30]) =< aux(2)
it(26) =< aux(3)
it(28) =< aux(3)
it([29]) =< aux(3)

with precondition: [V>=1,Out>=1,5*V+3>=2*Out,7*V>=2*Out+3]

#### Cost of chains of start(V,V1):
* Chain [33]: 2*s(1)+5*s(2)+6*s(6)+2*s(7)+4*s(8)+5
Such that:s(3) =< V
s(1) =< V+1
s(2) =< V/2+1/2
s(4) =< 5/2*V+3/2
s(5) =< 20/19*V+1/19
s(6) =< s(3)
s(2) =< s(3)
s(7) =< s(4)
s(8) =< s(4)
s(6) =< s(4)
s(2) =< s(4)
s(1) =< s(4)
s(8) =< s(5)
s(6) =< s(5)
s(2) =< s(5)

with precondition: []

Closed-form bounds of start(V,V1):
-------------------------------------
* Chain [33] with precondition: []
- Upper bound: nat(V)*6+5+nat(V+1)*2+nat(5/2*V+3/2)*6+nat(V/2+1/2)*5
- Complexity: n

### Maximum cost of start(V,V1): nat(V)*6+5+nat(V+1)*2+nat(5/2*V+3/2)*6+nat(V/2+1/2)*5
Asymptotic class: n
* Total analysis performed in 278 ms.

(0) Obligation:

(1) DependencyGraphProof (BOTH BOUNDS(ID, ID) transformation)

(2) Obligation:

(3) TrsToWeightedTrsProof (BOTH BOUNDS(ID, ID) transformation)

(4) Obligation:

(5) InnermostUnusableRulesProof (BOTH BOUNDS(ID, ID) transformation)

(6) Obligation:

(7) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)

(8) Obligation:

(9) CompletionProof (UPPER BOUND(ID) transformation)

(10) Obligation:

(11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID) transformation)

(12) Obligation:

(13) CompleteCoflocoProof (EQUIVALENT transformation)

(14) BOUNDS(1, n^1)